#include "Settings.h"
#include <list>
#include <iostream>
#include <fstream>
#include <vector>

#ifndef SOLVER_H_
#define SOLVER_H_

using namespace std;

// This solver is an instance of the 1/0 Knapsack problem that showcases 
// dynamic programming in its solution.  
//
// Dynamic programming is a technique used when a problem can be solved in 
// terms of optimal solutions of instance sub-problems.
// 
// The 0/1 Knapsack Problem is as follows: Given a set of items, each with
// a given value and cost, and a maximum cost C, determine the set of items that can
// be included in the knapsack set without exceeding cost C.  The problem 
// is additionally constrained such that there may be either 0 or 1 instance
// of a given item included in the knapsack. 
// 
// This solver uses a bottom-up approach to dynamic programming for solving 
// the 0/1 Knapsack problem, finding a solution in terms of optimal sub-problems.


// A class representing the items being considered for inclusion in the knapsack.
class Item
{
public:
	Item();
	Item(int cost, int value, int number);

	// The cost of this item.
	int Cost() { return myCost; }

	// The value of this item.
	int Value() { return myValue; }

	// An identifier for this item that is unique for the item's input set.
	int Number() { return myNumber; }

	// Format the Item's data in a string.
	string ToString();

	bool operator<(Item const& other) { return myNumber < other.myNumber; }

	// Copy the Item's data into a buffer.
	void Marshall(int* storage);

	// Create a copy of this item.
	Item* Copy();

private:
	int myCost;
	int myValue;
	int myNumber;
};

// A class representing a solution for the 0/1 knapsack problem.
class Solution
{
public:
	Solution();
	Solution(int cost, int value, Item* item, Solution* subSolution);
	~Solution();

	// Tests whether this solution contains an item labeled with itemNumber.
	bool ContainsItem(int itemNumber);

	// The value of this solution.
	int Value() { return myValue; }

	// The cost of this solution.
	int Cost() { return myCost; }

	// Format the data within this solution as a string.
	string ToString();

	// Copy the data representing this solution into an array of integers.
	void Marshall(int** data, int* len, int count);

	// Create a solution from an array of integers.
	static Solution* UnMarshall(int* data, int numberOfSolutions);

	// Create a deep copy of this solution.
	Solution* Copy();

private:
	int myValue;
	int myCost;

	// The item added to another solution to form this solution.
	Item* myItem;

	// The solution added to another item to form this solution.
	Solution* mySubSolution;
};

// A class implementing the solver algorithms for this instance.
class Solver
{
public:
	Solver(int argc, char** argv);

	//MPI based method to solve the 0/1 Knapsack problem.
	int Solve();

	void Finish(double time);
	
private:
	// The settings for this dwarf.
	Settings* SettingsContainer;

	// The maximal cost parameter as given on the first line of the input file.
	int MaximumCost;

	// The vector of items with their associated weights and values.
	vector<Item*>* Items;
	int* ItemWeight;
	int* ItemValue;

	// The optimal solutions for costs 0..MaximumCost after Solve() has returned.
	Solution** Answers;

	// The number of items in the input file.
	int ItemCount;



	// A function to find the vector of items with cost less than or equal to (LEQ) i.
	vector<Item*>* FindItemsLEQI(int i);

	// Read the Item data, one Item value and associated cost per line, 
    // into a list of Items.
	void ReadData();
};

#endif
